phpseclib/Math/BigInteger.php
- 1
<?php
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81 define('MATH_BIGINTEGER_MONTGOMERY', 0);
- 82
- 83
- 84
- 85 define('MATH_BIGINTEGER_BARRETT', 1);
- 86
- 87
- 88
- 89 define('MATH_BIGINTEGER_POWEROF2', 2);
- 90
- 91
- 92
- 93 define('MATH_BIGINTEGER_CLASSIC', 3);
- 94
- 95
- 96
- 97 define('MATH_BIGINTEGER_NONE', 4);
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111 define('MATH_BIGINTEGER_VALUE', 0);
- 112
- 113
- 114
- 115 define('MATH_BIGINTEGER_SIGN', 1);
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128 define('MATH_BIGINTEGER_VARIABLE', 0);
- 129
- 130
- 131
- 132 define('MATH_BIGINTEGER_DATA', 1);
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144 define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
- 145
- 146
- 147
- 148
- 149
- 150 define('MATH_BIGINTEGER_MODE_BCMATH', 2);
- 151
- 152
- 153
- 154
- 155
- 156 define('MATH_BIGINTEGER_MODE_GMP', 3);
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166 define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176 class Math_BigInteger
- 177 {
- 178
- 179
- 180
- 181
- 182
- 183
- 184 var $value;
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192 var $is_negative = false;
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200 var $precision = -1;
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208 var $bitmask = false;
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222 var $hex;
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246 function __construct($x = 0, $base = 10)
- 247 {
- 248 if (!defined('MATH_BIGINTEGER_MODE')) {
- 249 switch (true) {
- 250 case extension_loaded('gmp'):
- 251 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
- 252 break;
- 253 case extension_loaded('bcmath'):
- 254 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
- 255 break;
- 256 default:
- 257 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
- 258 }
- 259 }
- 260
- 261 if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
- 262
- 263 ob_start();
- 264 @phpinfo();
- 265 $content = ob_get_contents();
- 266 ob_end_clean();
- 267
- 268 preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
- 269
- 270 $versions = array();
- 271 if (!empty($matches[1])) {
- 272 for ($i = 0; $i < count($matches[1]); $i++) {
- 273 $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
- 274
- 275
- 276 if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
- 277 $versions[$matches[1][$i]] = $fullVersion;
- 278 } else {
- 279 $versions[$matches[1][$i]] = $m[0];
- 280 }
- 281 }
- 282 }
- 283
- 284
- 285 switch (true) {
- 286 case !isset($versions['Header']):
- 287 case !isset($versions['Library']):
- 288 case $versions['Header'] == $versions['Library']:
- 289 case version_compare($versions['Header'], '1.0.0') >= 0 && version_compare($versions['Library'], '1.0.0') >= 0:
- 290 define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
- 291 break;
- 292 default:
- 293 define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
- 294 }
- 295 }
- 296
- 297 if (!defined('PHP_INT_SIZE')) {
- 298 define('PHP_INT_SIZE', 4);
- 299 }
- 300
- 301 if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
- 302 switch (PHP_INT_SIZE) {
- 303 case 8:
- 304 define('MATH_BIGINTEGER_BASE', 31);
- 305 define('MATH_BIGINTEGER_BASE_FULL', 0x80000000);
- 306 define('MATH_BIGINTEGER_MAX_DIGIT', 0x7FFFFFFF);
- 307 define('MATH_BIGINTEGER_MSB', 0x40000000);
- 308
- 309 define('MATH_BIGINTEGER_MAX10', 1000000000);
- 310 define('MATH_BIGINTEGER_MAX10_LEN', 9);
- 311
- 312 define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 62));
- 313 break;
- 314
- 315 default:
- 316 define('MATH_BIGINTEGER_BASE', 26);
- 317 define('MATH_BIGINTEGER_BASE_FULL', 0x4000000);
- 318 define('MATH_BIGINTEGER_MAX_DIGIT', 0x3FFFFFF);
- 319 define('MATH_BIGINTEGER_MSB', 0x2000000);
- 320
- 321 define('MATH_BIGINTEGER_MAX10', 10000000);
- 322 define('MATH_BIGINTEGER_MAX10_LEN', 7);
- 323
- 324
- 325
- 326 define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 52));
- 327 }
- 328 }
- 329
- 330 switch (MATH_BIGINTEGER_MODE) {
- 331 case MATH_BIGINTEGER_MODE_GMP:
- 332 switch (true) {
- 333 case is_resource($x) && get_resource_type($x) == 'GMP integer':
- 334
- 335 case is_object($x) && get_class($x) == 'GMP':
- 336 $this->value = $x;
- 337 return;
- 338 }
- 339 $this->value = gmp_init(0);
- 340 break;
- 341 case MATH_BIGINTEGER_MODE_BCMATH:
- 342 $this->value = '0';
- 343 break;
- 344 default:
- 345 $this->value = array();
- 346 }
- 347
- 348
- 349
- 350 if (empty($x) && (abs($base) != 256 || $x !== '0')) {
- 351 return;
- 352 }
- 353
- 354 switch ($base) {
- 355 case -256:
- 356 if (ord($x[0]) & 0x80) {
- 357 $x = ~$x;
- 358 $this->is_negative = true;
- 359 }
- 360 case 256:
- 361 switch (MATH_BIGINTEGER_MODE) {
- 362 case MATH_BIGINTEGER_MODE_GMP:
- 363 $this->value = function_exists('gmp_import') ?
- 364 gmp_import($x) :
- 365 gmp_init('0x' . bin2hex($x));
- 366 if ($this->is_negative) {
- 367 $this->value = gmp_neg($this->value);
- 368 }
- 369 break;
- 370 case MATH_BIGINTEGER_MODE_BCMATH:
- 371
- 372 $len = (strlen($x) + 3) & 0xFFFFFFFC;
- 373
- 374 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
- 375
- 376 for ($i = 0; $i < $len; $i+= 4) {
- 377 $this->value = bcmul($this->value, '4294967296', 0);
- 378 $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
- 379 }
- 380
- 381 if ($this->is_negative) {
- 382 $this->value = '-' . $this->value;
- 383 }
- 384
- 385 break;
- 386
- 387 default:
- 388 while (strlen($x)) {
- 389 $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE));
- 390 }
- 391 }
- 392
- 393 if ($this->is_negative) {
- 394 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
- 395 $this->is_negative = false;
- 396 }
- 397 $temp = $this->add(new Math_BigInteger('-1'));
- 398 $this->value = $temp->value;
- 399 }
- 400 break;
- 401 case 16:
- 402 case -16:
- 403 if ($base > 0 && $x[0] == '-') {
- 404 $this->is_negative = true;
- 405 $x = substr($x, 1);
- 406 }
- 407
- 408 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
- 409
- 410 $is_negative = false;
- 411 if ($base < 0 && hexdec($x[0]) >= 8) {
- 412 $this->is_negative = $is_negative = true;
- 413 $x = bin2hex(~pack('H*', $x));
- 414 }
- 415
- 416 switch (MATH_BIGINTEGER_MODE) {
- 417 case MATH_BIGINTEGER_MODE_GMP:
- 418 $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
- 419 $this->value = gmp_init($temp);
- 420 $this->is_negative = false;
- 421 break;
- 422 case MATH_BIGINTEGER_MODE_BCMATH:
- 423 $x = (strlen($x) & 1) ? '0' . $x : $x;
- 424 $temp = new Math_BigInteger(pack('H*', $x), 256);
- 425 $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
- 426 $this->is_negative = false;
- 427 break;
- 428 default:
- 429 $x = (strlen($x) & 1) ? '0' . $x : $x;
- 430 $temp = new Math_BigInteger(pack('H*', $x), 256);
- 431 $this->value = $temp->value;
- 432 }
- 433
- 434 if ($is_negative) {
- 435 $temp = $this->add(new Math_BigInteger('-1'));
- 436 $this->value = $temp->value;
- 437 }
- 438 break;
- 439 case 10:
- 440 case -10:
- 441
- 442
- 443
- 444 $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
- 445
- 446 switch (MATH_BIGINTEGER_MODE) {
- 447 case MATH_BIGINTEGER_MODE_GMP:
- 448 $this->value = gmp_init($x);
- 449 break;
- 450 case MATH_BIGINTEGER_MODE_BCMATH:
- 451
- 452
- 453 $this->value = $x === '-' ? '0' : (string) $x;
- 454 break;
- 455 default:
- 456 $temp = new Math_BigInteger();
- 457
- 458 $multiplier = new Math_BigInteger();
- 459 $multiplier->value = array(MATH_BIGINTEGER_MAX10);
- 460
- 461 if ($x[0] == '-') {
- 462 $this->is_negative = true;
- 463 $x = substr($x, 1);
- 464 }
- 465
- 466 $x = str_pad($x, strlen($x) + ((MATH_BIGINTEGER_MAX10_LEN - 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT);
- 467 while (strlen($x)) {
- 468 $temp = $temp->multiply($multiplier);
- 469 $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256));
- 470 $x = substr($x, MATH_BIGINTEGER_MAX10_LEN);
- 471 }
- 472
- 473 $this->value = $temp->value;
- 474 }
- 475 break;
- 476 case 2:
- 477 case -2:
- 478 if ($base > 0 && $x[0] == '-') {
- 479 $this->is_negative = true;
- 480 $x = substr($x, 1);
- 481 }
- 482
- 483 $x = preg_replace('#^([01]*).*#', '$1', $x);
- 484 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
- 485
- 486 $str = '0x';
- 487 while (strlen($x)) {
- 488 $part = substr($x, 0, 4);
- 489 $str.= dechex(bindec($part));
- 490 $x = substr($x, 4);
- 491 }
- 492
- 493 if ($this->is_negative) {
- 494 $str = '-' . $str;
- 495 }
- 496
- 497 $temp = new Math_BigInteger($str, 8 * $base);
- 498 $this->value = $temp->value;
- 499 $this->is_negative = $temp->is_negative;
- 500
- 501 break;
- 502 default:
- 503
- 504 }
- 505 }
- 506
- 507
- 508
- 509
- 510
- 511
- 512
- 513
- 514
- 515 function Math_BigInteger($x = 0, $base = 10)
- 516 {
- 517 $this->__construct($x, $base);
- 518 }
- 519
- 520
- 521
- 522
- 523
- 524
- 525
- 526
- 527
- 528
- 529
- 530
- 531
- 532
- 533
- 534
- 535
- 536
- 537
- 538
- 539
- 540
- 541
- 542 function toBytes($twos_compliment = false)
- 543 {
- 544 if ($twos_compliment) {
- 545 $comparison = $this->compare(new Math_BigInteger());
- 546 if ($comparison == 0) {
- 547 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
- 548 }
- 549
- 550 $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy();
- 551 $bytes = $temp->toBytes();
- 552
- 553 if (empty($bytes)) {
- 554 $bytes = chr(0);
- 555 }
- 556
- 557 if (ord($bytes[0]) & 0x80) {
- 558 $bytes = chr(0) . $bytes;
- 559 }
- 560
- 561 return $comparison < 0 ? ~$bytes : $bytes;
- 562 }
- 563
- 564 switch (MATH_BIGINTEGER_MODE) {
- 565 case MATH_BIGINTEGER_MODE_GMP:
- 566 if (gmp_cmp($this->value, gmp_init(0)) == 0) {
- 567 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
- 568 }
- 569
- 570 if (function_exists('gmp_export')) {
- 571 $temp = gmp_export($this->value);
- 572 } else {
- 573 $temp = gmp_strval(gmp_abs($this->value), 16);
- 574 $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
- 575 $temp = pack('H*', $temp);
- 576 }
- 577
- 578 return $this->precision > 0 ?
- 579 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
- 580 ltrim($temp, chr(0));
- 581 case MATH_BIGINTEGER_MODE_BCMATH:
- 582 if ($this->value === '0') {
- 583 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
- 584 }
- 585
- 586 $value = '';
- 587 $current = $this->value;
- 588
- 589 if ($current[0] == '-') {
- 590 $current = substr($current, 1);
- 591 }
- 592
- 593 while (bccomp($current, '0', 0) > 0) {
- 594 $temp = bcmod($current, '16777216');
- 595 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
- 596 $current = bcdiv($current, '16777216', 0);
- 597 }
- 598
- 599 return $this->precision > 0 ?
- 600 substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
- 601 ltrim($value, chr(0));
- 602 }
- 603
- 604 if (!count($this->value)) {
- 605 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
- 606 }
- 607 $result = $this->_int2bytes($this->value[count($this->value) - 1]);
- 608
- 609 $temp = $this->copy();
- 610
- 611 for ($i = count($temp->value) - 2; $i >= 0; --$i) {
- 612 $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE);
- 613 $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
- 614 }
- 615
- 616 return $this->precision > 0 ?
- 617 str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
- 618 $result;
- 619 }
- 620
- 621
- 622
- 623
- 624
- 625
- 626
- 627
- 628
- 629
- 630
- 631
- 632
- 633
- 634
- 635
- 636
- 637
- 638
- 639
- 640
- 641
- 642
- 643 function toHex($twos_compliment = false)
- 644 {
- 645 return bin2hex($this->toBytes($twos_compliment));
- 646 }
- 647
- 648
- 649
- 650
- 651
- 652
- 653
- 654
- 655
- 656
- 657
- 658
- 659
- 660
- 661
- 662
- 663
- 664
- 665
- 666
- 667
- 668
- 669
- 670 function toBits($twos_compliment = false)
- 671 {
- 672 $hex = $this->toHex($twos_compliment);
- 673 $bits = '';
- 674 for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
- 675 $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
- 676 }
- 677 if ($start) {
- 678 $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
- 679 }
- 680 $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
- 681
- 682 if ($twos_compliment && $this->compare(new Math_BigInteger()) > 0 && $this->precision <= 0) {
- 683 return '0' . $result;
- 684 }
- 685
- 686 return $result;
- 687 }
- 688
- 689
- 690
- 691
- 692
- 693
- 694
- 695
- 696
- 697
- 698
- 699
- 700
- 701
- 702
- 703
- 704
- 705
- 706
- 707 function toString()
- 708 {
- 709 switch (MATH_BIGINTEGER_MODE) {
- 710 case MATH_BIGINTEGER_MODE_GMP:
- 711 return gmp_strval($this->value);
- 712 case MATH_BIGINTEGER_MODE_BCMATH:
- 713 if ($this->value === '0') {
- 714 return '0';
- 715 }
- 716
- 717 return ltrim($this->value, '0');
- 718 }
- 719
- 720 if (!count($this->value)) {
- 721 return '0';
- 722 }
- 723
- 724 $temp = $this->copy();
- 725 $temp->is_negative = false;
- 726
- 727 $divisor = new Math_BigInteger();
- 728 $divisor->value = array(MATH_BIGINTEGER_MAX10);
- 729 $result = '';
- 730 while (count($temp->value)) {
- 731 list($temp, $mod) = $temp->divide($divisor);
- 732 $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', MATH_BIGINTEGER_MAX10_LEN, '0', STR_PAD_LEFT) . $result;
- 733 }
- 734 $result = ltrim($result, '0');
- 735 if (empty($result)) {
- 736 $result = '0';
- 737 }
- 738
- 739 if ($this->is_negative) {
- 740 $result = '-' . $result;
- 741 }
- 742
- 743 return $result;
- 744 }
- 745
- 746
- 747
- 748
- 749
- 750
- 751
- 752
- 753
- 754
- 755
- 756
- 757
- 758 function copy()
- 759 {
- 760 $temp = new Math_BigInteger();
- 761 $temp->value = $this->value;
- 762 $temp->is_negative = $this->is_negative;
- 763 $temp->precision = $this->precision;
- 764 $temp->bitmask = $this->bitmask;
- 765 return $temp;
- 766 }
- 767
- 768
- 769
- 770
- 771
- 772
- 773
- 774
- 775
- 776
- 777 function __toString()
- 778 {
- 779 return $this->toString();
- 780 }
- 781
- 782
- 783
- 784
- 785
- 786
- 787
- 788
- 789
- 790
- 791
- 792
- 793
- 794 function __clone()
- 795 {
- 796 return $this->copy();
- 797 }
- 798
- 799
- 800
- 801
- 802
- 803
- 804
- 805
- 806
- 807 function __sleep()
- 808 {
- 809 $this->hex = $this->toHex(true);
- 810 $vars = array('hex');
- 811 if ($this->precision > 0) {
- 812 $vars[] = 'precision';
- 813 }
- 814 return $vars;
- 815 }
- 816
- 817
- 818
- 819
- 820
- 821
- 822
- 823
- 824
- 825 function __wakeup()
- 826 {
- 827 $temp = new Math_BigInteger($this->hex, -16);
- 828 $this->value = $temp->value;
- 829 $this->is_negative = $temp->is_negative;
- 830 if ($this->precision > 0) {
- 831
- 832 $this->setPrecision($this->precision);
- 833 }
- 834 }
- 835
- 836
- 837
- 838
- 839
- 840
- 841
- 842
- 843 function __debugInfo()
- 844 {
- 845 $opts = array();
- 846 switch (MATH_BIGINTEGER_MODE) {
- 847 case MATH_BIGINTEGER_MODE_GMP:
- 848 $engine = 'gmp';
- 849 break;
- 850 case MATH_BIGINTEGER_MODE_BCMATH:
- 851 $engine = 'bcmath';
- 852 break;
- 853 case MATH_BIGINTEGER_MODE_INTERNAL:
- 854 $engine = 'internal';
- 855 $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
- 856 }
- 857 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
- 858 $opts[] = 'OpenSSL';
- 859 }
- 860 if (!empty($opts)) {
- 861 $engine.= ' (' . implode($opts, ', ') . ')';
- 862 }
- 863 return array(
- 864 'value' => '0x' . $this->toHex(true),
- 865 'engine' => $engine
- 866 );
- 867 }
- 868
- 869
- 870
- 871
- 872
- 873
- 874
- 875
- 876
- 877
- 878
- 879
- 880
- 881
- 882
- 883
- 884
- 885
- 886
- 887
- 888
- 889
- 890
- 891 function add($y)
- 892 {
- 893 switch (MATH_BIGINTEGER_MODE) {
- 894 case MATH_BIGINTEGER_MODE_GMP:
- 895 $temp = new Math_BigInteger();
- 896 $temp->value = gmp_add($this->value, $y->value);
- 897
- 898 return $this->_normalize($temp);
- 899 case MATH_BIGINTEGER_MODE_BCMATH:
- 900 $temp = new Math_BigInteger();
- 901 $temp->value = bcadd($this->value, $y->value, 0);
- 902
- 903 return $this->_normalize($temp);
- 904 }
- 905
- 906 $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
- 907
- 908 $result = new Math_BigInteger();
- 909 $result->value = $temp[MATH_BIGINTEGER_VALUE];
- 910 $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
- 911
- 912 return $this->_normalize($result);
- 913 }
- 914
- 915
- 916
- 917
- 918
- 919
- 920
- 921
- 922
- 923
- 924
- 925 function _add($x_value, $x_negative, $y_value, $y_negative)
- 926 {
- 927 $x_size = count($x_value);
- 928 $y_size = count($y_value);
- 929
- 930 if ($x_size == 0) {
- 931 return array(
- 932 MATH_BIGINTEGER_VALUE => $y_value,
- 933 MATH_BIGINTEGER_SIGN => $y_negative
- 934 );
- 935 } elseif ($y_size == 0) {
- 936 return array(
- 937 MATH_BIGINTEGER_VALUE => $x_value,
- 938 MATH_BIGINTEGER_SIGN => $x_negative
- 939 );
- 940 }
- 941
- 942
- 943 if ($x_negative != $y_negative) {
- 944 if ($x_value == $y_value) {
- 945 return array(
- 946 MATH_BIGINTEGER_VALUE => array(),
- 947 MATH_BIGINTEGER_SIGN => false
- 948 );
- 949 }
- 950
- 951 $temp = $this->_subtract($x_value, false, $y_value, false);
- 952 $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
- 953 $x_negative : $y_negative;
- 954
- 955 return $temp;
- 956 }
- 957
- 958 if ($x_size < $y_size) {
- 959 $size = $x_size;
- 960 $value = $y_value;
- 961 } else {
- 962 $size = $y_size;
- 963 $value = $x_value;
- 964 }
- 965
- 966 $value[count($value)] = 0;
- 967
- 968 $carry = 0;
- 969 for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
- 970 $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry;
- 971 $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT2;
- 972 $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
- 973
- 974 $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
- 975
- 976 $value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
- 977 $value[$j] = $temp;
- 978 }
- 979
- 980 if ($j == $size) {
- 981 $sum = $x_value[$i] + $y_value[$i] + $carry;
- 982 $carry = $sum >= MATH_BIGINTEGER_BASE_FULL;
- 983 $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum;
- 984 ++$i;
- 985 }
- 986
- 987 if ($carry) {
- 988 for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) {
- 989 $value[$i] = 0;
- 990 }
- 991 ++$value[$i];
- 992 }
- 993
- 994 return array(
- 995 MATH_BIGINTEGER_VALUE => $this->_trim($value),
- 996 MATH_BIGINTEGER_SIGN => $x_negative
- 997 );
- 998 }
- 999
- 1000
- 1001
- 1002
- 1003
- 1004
- 1005
- 1006
- 1007
- 1008
- 1009
- 1010
- 1011
- 1012
- 1013
- 1014
- 1015
- 1016
- 1017
- 1018
- 1019
- 1020
- 1021
- 1022 function subtract($y)
- 1023 {
- 1024 switch (MATH_BIGINTEGER_MODE) {
- 1025 case MATH_BIGINTEGER_MODE_GMP:
- 1026 $temp = new Math_BigInteger();
- 1027 $temp->value = gmp_sub($this->value, $y->value);
- 1028
- 1029 return $this->_normalize($temp);
- 1030 case MATH_BIGINTEGER_MODE_BCMATH:
- 1031 $temp = new Math_BigInteger();
- 1032 $temp->value = bcsub($this->value, $y->value, 0);
- 1033
- 1034 return $this->_normalize($temp);
- 1035 }
- 1036
- 1037 $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
- 1038
- 1039 $result = new Math_BigInteger();
- 1040 $result->value = $temp[MATH_BIGINTEGER_VALUE];
- 1041 $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
- 1042
- 1043 return $this->_normalize($result);
- 1044 }
- 1045
- 1046
- 1047
- 1048
- 1049
- 1050
- 1051
- 1052
- 1053
- 1054
- 1055
- 1056 function _subtract($x_value, $x_negative, $y_value, $y_negative)
- 1057 {
- 1058 $x_size = count($x_value);
- 1059 $y_size = count($y_value);
- 1060
- 1061 if ($x_size == 0) {
- 1062 return array(
- 1063 MATH_BIGINTEGER_VALUE => $y_value,
- 1064 MATH_BIGINTEGER_SIGN => !$y_negative
- 1065 );
- 1066 } elseif ($y_size == 0) {
- 1067 return array(
- 1068 MATH_BIGINTEGER_VALUE => $x_value,
- 1069 MATH_BIGINTEGER_SIGN => $x_negative
- 1070 );
- 1071 }
- 1072
- 1073
- 1074 if ($x_negative != $y_negative) {
- 1075 $temp = $this->_add($x_value, false, $y_value, false);
- 1076 $temp[MATH_BIGINTEGER_SIGN] = $x_negative;
- 1077
- 1078 return $temp;
- 1079 }
- 1080
- 1081 $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
- 1082
- 1083 if (!$diff) {
- 1084 return array(
- 1085 MATH_BIGINTEGER_VALUE => array(),
- 1086 MATH_BIGINTEGER_SIGN => false
- 1087 );
- 1088 }
- 1089
- 1090
- 1091 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
- 1092 $temp = $x_value;
- 1093 $x_value = $y_value;
- 1094 $y_value = $temp;
- 1095
- 1096 $x_negative = !$x_negative;
- 1097
- 1098 $x_size = count($x_value);
- 1099 $y_size = count($y_value);
- 1100 }
- 1101
- 1102
- 1103
- 1104 $carry = 0;
- 1105 for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
- 1106 $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry;
- 1107 $carry = $sum < 0;
- 1108 $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
- 1109
- 1110 $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
- 1111
- 1112 $x_value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
- 1113 $x_value[$j] = $temp;
- 1114 }
- 1115
- 1116 if ($j == $y_size) {
- 1117 $sum = $x_value[$i] - $y_value[$i] - $carry;
- 1118 $carry = $sum < 0;
- 1119 $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum;
- 1120 ++$i;
- 1121 }
- 1122
- 1123 if ($carry) {
- 1124 for (; !$x_value[$i]; ++$i) {
- 1125 $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
- 1126 }
- 1127 --$x_value[$i];
- 1128 }
- 1129
- 1130 return array(
- 1131 MATH_BIGINTEGER_VALUE => $this->_trim($x_value),
- 1132 MATH_BIGINTEGER_SIGN => $x_negative
- 1133 );
- 1134 }
- 1135
- 1136
- 1137
- 1138
- 1139
- 1140
- 1141
- 1142
- 1143
- 1144
- 1145
- 1146
- 1147
- 1148
- 1149
- 1150
- 1151
- 1152
- 1153
- 1154
- 1155
- 1156
- 1157 function multiply($x)
- 1158 {
- 1159 switch (MATH_BIGINTEGER_MODE) {
- 1160 case MATH_BIGINTEGER_MODE_GMP:
- 1161 $temp = new Math_BigInteger();
- 1162 $temp->value = gmp_mul($this->value, $x->value);
- 1163
- 1164 return $this->_normalize($temp);
- 1165 case MATH_BIGINTEGER_MODE_BCMATH:
- 1166 $temp = new Math_BigInteger();
- 1167 $temp->value = bcmul($this->value, $x->value, 0);
- 1168
- 1169 return $this->_normalize($temp);
- 1170 }
- 1171
- 1172 $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
- 1173
- 1174 $product = new Math_BigInteger();
- 1175 $product->value = $temp[MATH_BIGINTEGER_VALUE];
- 1176 $product->is_negative = $temp[MATH_BIGINTEGER_SIGN];
- 1177
- 1178 return $this->_normalize($product);
- 1179 }
- 1180
- 1181
- 1182
- 1183
- 1184
- 1185
- 1186
- 1187
- 1188
- 1189
- 1190
- 1191 function _multiply($x_value, $x_negative, $y_value, $y_negative)
- 1192 {
- 1193
- 1194
- 1195
- 1196
- 1197
- 1198
- 1199
- 1200 $x_length = count($x_value);
- 1201 $y_length = count($y_value);
- 1202
- 1203 if (!$x_length || !$y_length) {
- 1204 return array(
- 1205 MATH_BIGINTEGER_VALUE => array(),
- 1206 MATH_BIGINTEGER_SIGN => false
- 1207 );
- 1208 }
- 1209
- 1210 return array(
- 1211 MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
- 1212 $this->_trim($this->_regularMultiply($x_value, $y_value)) :
- 1213 $this->_trim($this->_karatsuba($x_value, $y_value)),
- 1214 MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
- 1215 );
- 1216 }
- 1217
- 1218
- 1219
- 1220
- 1221
- 1222
- 1223
- 1224
- 1225
- 1226
- 1227
- 1228 function _regularMultiply($x_value, $y_value)
- 1229 {
- 1230 $x_length = count($x_value);
- 1231 $y_length = count($y_value);
- 1232
- 1233 if (!$x_length || !$y_length) {
- 1234 return array();
- 1235 }
- 1236
- 1237 if ($x_length < $y_length) {
- 1238 $temp = $x_value;
- 1239 $x_value = $y_value;
- 1240 $y_value = $temp;
- 1241
- 1242 $x_length = count($x_value);
- 1243 $y_length = count($y_value);
- 1244 }
- 1245
- 1246 $product_value = $this->_array_repeat(0, $x_length + $y_length);
- 1247
- 1248
- 1249
- 1250
- 1251
- 1252
- 1253
- 1254 $carry = 0;
- 1255
- 1256 for ($j = 0; $j < $x_length; ++$j) {
- 1257 $temp = $x_value[$j] * $y_value[0] + $carry;
- 1258 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 1259 $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
- 1260 }
- 1261
- 1262 $product_value[$j] = $carry;
- 1263
- 1264
- 1265
- 1266 for ($i = 1; $i < $y_length; ++$i) {
- 1267 $carry = 0;
- 1268
- 1269 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
- 1270 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
- 1271 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 1272 $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
- 1273 }
- 1274
- 1275 $product_value[$k] = $carry;
- 1276 }
- 1277
- 1278 return $product_value;
- 1279 }
- 1280
- 1281
- 1282
- 1283
- 1284
- 1285
- 1286
- 1287
- 1288
- 1289
- 1290
- 1291
- 1292 function _karatsuba($x_value, $y_value)
- 1293 {
- 1294 $m = min(count($x_value) >> 1, count($y_value) >> 1);
- 1295
- 1296 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
- 1297 return $this->_regularMultiply($x_value, $y_value);
- 1298 }
- 1299
- 1300 $x1 = array_slice($x_value, $m);
- 1301 $x0 = array_slice($x_value, 0, $m);
- 1302 $y1 = array_slice($y_value, $m);
- 1303 $y0 = array_slice($y_value, 0, $m);
- 1304
- 1305 $z2 = $this->_karatsuba($x1, $y1);
- 1306 $z0 = $this->_karatsuba($x0, $y0);
- 1307
- 1308 $z1 = $this->_add($x1, false, $x0, false);
- 1309 $temp = $this->_add($y1, false, $y0, false);
- 1310 $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
- 1311 $temp = $this->_add($z2, false, $z0, false);
- 1312 $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
- 1313
- 1314 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
- 1315 $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
- 1316
- 1317 $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
- 1318 $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false);
- 1319
- 1320 return $xy[MATH_BIGINTEGER_VALUE];
- 1321 }
- 1322
- 1323
- 1324
- 1325
- 1326
- 1327
- 1328
- 1329
- 1330 function _square($x = false)
- 1331 {
- 1332 return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
- 1333 $this->_trim($this->_baseSquare($x)) :
- 1334 $this->_trim($this->_karatsubaSquare($x));
- 1335 }
- 1336
- 1337
- 1338
- 1339
- 1340
- 1341
- 1342
- 1343
- 1344
- 1345
- 1346
- 1347
- 1348 function _baseSquare($value)
- 1349 {
- 1350 if (empty($value)) {
- 1351 return array();
- 1352 }
- 1353 $square_value = $this->_array_repeat(0, 2 * count($value));
- 1354
- 1355 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
- 1356 $i2 = $i << 1;
- 1357
- 1358 $temp = $square_value[$i2] + $value[$i] * $value[$i];
- 1359 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 1360 $square_value[$i2] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
- 1361
- 1362
- 1363 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
- 1364 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
- 1365 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 1366 $square_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
- 1367 }
- 1368
- 1369
- 1370
- 1371 $square_value[$i + $max_index + 1] = $carry;
- 1372 }
- 1373
- 1374 return $square_value;
- 1375 }
- 1376
- 1377
- 1378
- 1379
- 1380
- 1381
- 1382
- 1383
- 1384
- 1385
- 1386
- 1387 function _karatsubaSquare($value)
- 1388 {
- 1389 $m = count($value) >> 1;
- 1390
- 1391 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
- 1392 return $this->_baseSquare($value);
- 1393 }
- 1394
- 1395 $x1 = array_slice($value, $m);
- 1396 $x0 = array_slice($value, 0, $m);
- 1397
- 1398 $z2 = $this->_karatsubaSquare($x1);
- 1399 $z0 = $this->_karatsubaSquare($x0);
- 1400
- 1401 $z1 = $this->_add($x1, false, $x0, false);
- 1402 $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
- 1403 $temp = $this->_add($z2, false, $z0, false);
- 1404 $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
- 1405
- 1406 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
- 1407 $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
- 1408
- 1409 $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
- 1410 $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false);
- 1411
- 1412 return $xx[MATH_BIGINTEGER_VALUE];
- 1413 }
- 1414
- 1415
- 1416
- 1417
- 1418
- 1419
- 1420
- 1421
- 1422
- 1423
- 1424
- 1425
- 1426
- 1427
- 1428
- 1429
- 1430
- 1431
- 1432
- 1433
- 1434
- 1435
- 1436
- 1437
- 1438
- 1439
- 1440
- 1441
- 1442
- 1443
- 1444 function divide($y)
- 1445 {
- 1446 switch (MATH_BIGINTEGER_MODE) {
- 1447 case MATH_BIGINTEGER_MODE_GMP:
- 1448 $quotient = new Math_BigInteger();
- 1449 $remainder = new Math_BigInteger();
- 1450
- 1451 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
- 1452
- 1453 if (gmp_sign($remainder->value) < 0) {
- 1454 $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
- 1455 }
- 1456
- 1457 return array($this->_normalize($quotient), $this->_normalize($remainder));
- 1458 case MATH_BIGINTEGER_MODE_BCMATH:
- 1459 $quotient = new Math_BigInteger();
- 1460 $remainder = new Math_BigInteger();
- 1461
- 1462 $quotient->value = bcdiv($this->value, $y->value, 0);
- 1463 $remainder->value = bcmod($this->value, $y->value);
- 1464
- 1465 if ($remainder->value[0] == '-') {
- 1466 $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
- 1467 }
- 1468
- 1469 return array($this->_normalize($quotient), $this->_normalize($remainder));
- 1470 }
- 1471
- 1472 if (count($y->value) == 1) {
- 1473 list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
- 1474 $quotient = new Math_BigInteger();
- 1475 $remainder = new Math_BigInteger();
- 1476 $quotient->value = $q;
- 1477 $remainder->value = array($r);
- 1478 $quotient->is_negative = $this->is_negative != $y->is_negative;
- 1479 return array($this->_normalize($quotient), $this->_normalize($remainder));
- 1480 }
- 1481
- 1482 static $zero;
- 1483 if (!isset($zero)) {
- 1484 $zero = new Math_BigInteger();
- 1485 }
- 1486
- 1487 $x = $this->copy();
- 1488 $y = $y->copy();
- 1489
- 1490 $x_sign = $x->is_negative;
- 1491 $y_sign = $y->is_negative;
- 1492
- 1493 $x->is_negative = $y->is_negative = false;
- 1494
- 1495 $diff = $x->compare($y);
- 1496
- 1497 if (!$diff) {
- 1498 $temp = new Math_BigInteger();
- 1499 $temp->value = array(1);
- 1500 $temp->is_negative = $x_sign != $y_sign;
- 1501 return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
- 1502 }
- 1503
- 1504 if ($diff < 0) {
- 1505
- 1506 if ($x_sign) {
- 1507 $x = $y->subtract($x);
- 1508 }
- 1509 return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
- 1510 }
- 1511
- 1512
- 1513 $msb = $y->value[count($y->value) - 1];
- 1514 for ($shift = 0; !($msb & MATH_BIGINTEGER_MSB); ++$shift) {
- 1515 $msb <<= 1;
- 1516 }
- 1517 $x->_lshift($shift);
- 1518 $y->_lshift($shift);
- 1519 $y_value = &$y->value;
- 1520
- 1521 $x_max = count($x->value) - 1;
- 1522 $y_max = count($y->value) - 1;
- 1523
- 1524 $quotient = new Math_BigInteger();
- 1525 $quotient_value = &$quotient->value;
- 1526 $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
- 1527
- 1528 static $temp, $lhs, $rhs;
- 1529 if (!isset($temp)) {
- 1530 $temp = new Math_BigInteger();
- 1531 $lhs = new Math_BigInteger();
- 1532 $rhs = new Math_BigInteger();
- 1533 }
- 1534 $temp_value = &$temp->value;
- 1535 $rhs_value = &$rhs->value;
- 1536
- 1537
- 1538 $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
- 1539
- 1540 while ($x->compare($temp) >= 0) {
- 1541
- 1542 ++$quotient_value[$x_max - $y_max];
- 1543 $x = $x->subtract($temp);
- 1544 $x_max = count($x->value) - 1;
- 1545 }
- 1546
- 1547 for ($i = $x_max; $i >= $y_max + 1; --$i) {
- 1548 $x_value = &$x->value;
- 1549 $x_window = array(
- 1550 isset($x_value[$i]) ? $x_value[$i] : 0,
- 1551 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
- 1552 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
- 1553 );
- 1554 $y_window = array(
- 1555 $y_value[$y_max],
- 1556 ($y_max > 0) ? $y_value[$y_max - 1] : 0
- 1557 );
- 1558
- 1559 $q_index = $i - $y_max - 1;
- 1560 if ($x_window[0] == $y_window[0]) {
- 1561 $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT;
- 1562 } else {
- 1563 $quotient_value[$q_index] = $this->_safe_divide(
- 1564 $x_window[0] * MATH_BIGINTEGER_BASE_FULL + $x_window[1],
- 1565 $y_window[0]
- 1566 );
- 1567 }
- 1568
- 1569 $temp_value = array($y_window[1], $y_window[0]);
- 1570
- 1571 $lhs->value = array($quotient_value[$q_index]);
- 1572 $lhs = $lhs->multiply($temp);
- 1573
- 1574 $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
- 1575
- 1576 while ($lhs->compare($rhs) > 0) {
- 1577 --$quotient_value[$q_index];
- 1578
- 1579 $lhs->value = array($quotient_value[$q_index]);
- 1580 $lhs = $lhs->multiply($temp);
- 1581 }
- 1582
- 1583 $adjust = $this->_array_repeat(0, $q_index);
- 1584 $temp_value = array($quotient_value[$q_index]);
- 1585 $temp = $temp->multiply($y);
- 1586 $temp_value = &$temp->value;
- 1587 $temp_value = array_merge($adjust, $temp_value);
- 1588
- 1589 $x = $x->subtract($temp);
- 1590
- 1591 if ($x->compare($zero) < 0) {
- 1592 $temp_value = array_merge($adjust, $y_value);
- 1593 $x = $x->add($temp);
- 1594
- 1595 --$quotient_value[$q_index];
- 1596 }
- 1597
- 1598 $x_max = count($x_value) - 1;
- 1599 }
- 1600
- 1601
- 1602 $x->_rshift($shift);
- 1603
- 1604 $quotient->is_negative = $x_sign != $y_sign;
- 1605
- 1606
- 1607 if ($x_sign) {
- 1608 $y->_rshift($shift);
- 1609 $x = $y->subtract($x);
- 1610 }
- 1611
- 1612 return array($this->_normalize($quotient), $this->_normalize($x));
- 1613 }
- 1614
- 1615
- 1616
- 1617
- 1618
- 1619
- 1620
- 1621
- 1622
- 1623
- 1624
- 1625 function _divide_digit($dividend, $divisor)
- 1626 {
- 1627 $carry = 0;
- 1628 $result = array();
- 1629
- 1630 for ($i = count($dividend) - 1; $i >= 0; --$i) {
- 1631 $temp = MATH_BIGINTEGER_BASE_FULL * $carry + $dividend[$i];
- 1632 $result[$i] = $this->_safe_divide($temp, $divisor);
- 1633 $carry = (int) ($temp - $divisor * $result[$i]);
- 1634 }
- 1635
- 1636 return array($result, $carry);
- 1637 }
- 1638
- 1639
- 1640
- 1641
- 1642
- 1643
- 1644
- 1645
- 1646
- 1647
- 1648
- 1649
- 1650
- 1651
- 1652
- 1653
- 1654
- 1655
- 1656
- 1657
- 1658
- 1659
- 1660
- 1661
- 1662
- 1663
- 1664
- 1665
- 1666
- 1667
- 1668
- 1669
- 1670
- 1671
- 1672
- 1673
- 1674
- 1675
- 1676
- 1677
- 1678
- 1679
- 1680
- 1681 function modPow($e, $n)
- 1682 {
- 1683 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
- 1684
- 1685 if ($e->compare(new Math_BigInteger()) < 0) {
- 1686 $e = $e->abs();
- 1687
- 1688 $temp = $this->modInverse($n);
- 1689 if ($temp === false) {
- 1690 return false;
- 1691 }
- 1692
- 1693 return $this->_normalize($temp->modPow($e, $n));
- 1694 }
- 1695
- 1696 if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP) {
- 1697 $temp = new Math_BigInteger();
- 1698 $temp->value = gmp_powm($this->value, $e->value, $n->value);
- 1699
- 1700 return $this->_normalize($temp);
- 1701 }
- 1702
- 1703 if ($this->compare(new Math_BigInteger()) < 0 || $this->compare($n) > 0) {
- 1704 list(, $temp) = $this->divide($n);
- 1705 return $temp->modPow($e, $n);
- 1706 }
- 1707
- 1708 if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
- 1709 $components = array(
- 1710 'modulus' => $n->toBytes(true),
- 1711 'publicExponent' => $e->toBytes(true)
- 1712 );
- 1713
- 1714 $components = array(
- 1715 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
- 1716 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
- 1717 );
- 1718
- 1719 $RSAPublicKey = pack(
- 1720 'Ca*a*a*',
- 1721 48,
- 1722 $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
- 1723 $components['modulus'],
- 1724 $components['publicExponent']
- 1725 );
- 1726
- 1727 $rsaOID = pack('H*', '300d06092a864886f70d0101010500');
- 1728 $RSAPublicKey = chr(0) . $RSAPublicKey;
- 1729 $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
- 1730
- 1731 $encapsulated = pack(
- 1732 'Ca*a*',
- 1733 48,
- 1734 $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
- 1735 $rsaOID . $RSAPublicKey
- 1736 );
- 1737
- 1738 $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
- 1739 chunk_split(base64_encode($encapsulated)) .
- 1740 '-----END PUBLIC KEY-----';
- 1741
- 1742 $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
- 1743
- 1744 if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
- 1745 return new Math_BigInteger($result, 256);
- 1746 }
- 1747 }
- 1748
- 1749 if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
- 1750 $temp = new Math_BigInteger();
- 1751 $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
- 1752
- 1753 return $this->_normalize($temp);
- 1754 }
- 1755
- 1756 if (empty($e->value)) {
- 1757 $temp = new Math_BigInteger();
- 1758 $temp->value = array(1);
- 1759 return $this->_normalize($temp);
- 1760 }
- 1761
- 1762 if ($e->value == array(1)) {
- 1763 list(, $temp) = $this->divide($n);
- 1764 return $this->_normalize($temp);
- 1765 }
- 1766
- 1767 if ($e->value == array(2)) {
- 1768 $temp = new Math_BigInteger();
- 1769 $temp->value = $this->_square($this->value);
- 1770 list(, $temp) = $temp->divide($n);
- 1771 return $this->_normalize($temp);
- 1772 }
- 1773
- 1774 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
- 1775
- 1776
- 1777
- 1778
- 1779
- 1780
- 1781
- 1782 if ($n->value[0] & 1) {
- 1783 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
- 1784 }
- 1785
- 1786
- 1787
- 1788 for ($i = 0; $i < count($n->value); ++$i) {
- 1789 if ($n->value[$i]) {
- 1790 $temp = decbin($n->value[$i]);
- 1791 $j = strlen($temp) - strrpos($temp, '1') - 1;
- 1792 $j+= 26 * $i;
- 1793 break;
- 1794 }
- 1795 }
- 1796
- 1797
- 1798 $mod1 = $n->copy();
- 1799 $mod1->_rshift($j);
- 1800 $mod2 = new Math_BigInteger();
- 1801 $mod2->value = array(1);
- 1802 $mod2->_lshift($j);
- 1803
- 1804 $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
- 1805 $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
- 1806
- 1807 $y1 = $mod2->modInverse($mod1);
- 1808 $y2 = $mod1->modInverse($mod2);
- 1809
- 1810 $result = $part1->multiply($mod2);
- 1811 $result = $result->multiply($y1);
- 1812
- 1813 $temp = $part2->multiply($mod1);
- 1814 $temp = $temp->multiply($y2);
- 1815
- 1816 $result = $result->add($temp);
- 1817 list(, $result) = $result->divide($n);
- 1818
- 1819 return $this->_normalize($result);
- 1820 }
- 1821
- 1822
- 1823
- 1824
- 1825
- 1826
- 1827
- 1828
- 1829
- 1830
- 1831
- 1832 function powMod($e, $n)
- 1833 {
- 1834 return $this->modPow($e, $n);
- 1835 }
- 1836
- 1837
- 1838
- 1839
- 1840
- 1841
- 1842
- 1843
- 1844
- 1845
- 1846
- 1847
- 1848
- 1849
- 1850
- 1851 function _slidingWindow($e, $n, $mode)
- 1852 {
- 1853 static $window_ranges = array(7, 25, 81, 241, 673, 1793);
- 1854
- 1855
- 1856 $e_value = $e->value;
- 1857 $e_length = count($e_value) - 1;
- 1858 $e_bits = decbin($e_value[$e_length]);
- 1859 for ($i = $e_length - 1; $i >= 0; --$i) {
- 1860 $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE, '0', STR_PAD_LEFT);
- 1861 }
- 1862
- 1863 $e_length = strlen($e_bits);
- 1864
- 1865
- 1866
- 1867 for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) {
- 1868 }
- 1869
- 1870 $n_value = $n->value;
- 1871
- 1872
- 1873 $powers = array();
- 1874 $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
- 1875 $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
- 1876
- 1877
- 1878
- 1879 $temp = 1 << ($window_size - 1);
- 1880 for ($i = 1; $i < $temp; ++$i) {
- 1881 $i2 = $i << 1;
- 1882 $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
- 1883 }
- 1884
- 1885 $result = array(1);
- 1886 $result = $this->_prepareReduce($result, $n_value, $mode);
- 1887
- 1888 for ($i = 0; $i < $e_length;) {
- 1889 if (!$e_bits[$i]) {
- 1890 $result = $this->_squareReduce($result, $n_value, $mode);
- 1891 ++$i;
- 1892 } else {
- 1893 for ($j = $window_size - 1; $j > 0; --$j) {
- 1894 if (!empty($e_bits[$i + $j])) {
- 1895 break;
- 1896 }
- 1897 }
- 1898
- 1899
- 1900 for ($k = 0; $k <= $j; ++$k) {
- 1901 $result = $this->_squareReduce($result, $n_value, $mode);
- 1902 }
- 1903
- 1904 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
- 1905
- 1906 $i += $j + 1;
- 1907 }
- 1908 }
- 1909
- 1910 $temp = new Math_BigInteger();
- 1911 $temp->value = $this->_reduce($result, $n_value, $mode);
- 1912
- 1913 return $temp;
- 1914 }
- 1915
- 1916
- 1917
- 1918
- 1919
- 1920
- 1921
- 1922
- 1923
- 1924
- 1925
- 1926
- 1927
- 1928 function _reduce($x, $n, $mode)
- 1929 {
- 1930 switch ($mode) {
- 1931 case MATH_BIGINTEGER_MONTGOMERY:
- 1932 return $this->_montgomery($x, $n);
- 1933 case MATH_BIGINTEGER_BARRETT:
- 1934 return $this->_barrett($x, $n);
- 1935 case MATH_BIGINTEGER_POWEROF2:
- 1936 $lhs = new Math_BigInteger();
- 1937 $lhs->value = $x;
- 1938 $rhs = new Math_BigInteger();
- 1939 $rhs->value = $n;
- 1940 return $x->_mod2($n);
- 1941 case MATH_BIGINTEGER_CLASSIC:
- 1942 $lhs = new Math_BigInteger();
- 1943 $lhs->value = $x;
- 1944 $rhs = new Math_BigInteger();
- 1945 $rhs->value = $n;
- 1946 list(, $temp) = $lhs->divide($rhs);
- 1947 return $temp->value;
- 1948 case MATH_BIGINTEGER_NONE:
- 1949 return $x;
- 1950 default:
- 1951
- 1952 }
- 1953 }
- 1954
- 1955
- 1956
- 1957
- 1958
- 1959
- 1960
- 1961
- 1962
- 1963
- 1964
- 1965 function _prepareReduce($x, $n, $mode)
- 1966 {
- 1967 if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
- 1968 return $this->_prepMontgomery($x, $n);
- 1969 }
- 1970 return $this->_reduce($x, $n, $mode);
- 1971 }
- 1972
- 1973
- 1974
- 1975
- 1976
- 1977
- 1978
- 1979
- 1980
- 1981
- 1982
- 1983
- 1984 function _multiplyReduce($x, $y, $n, $mode)
- 1985 {
- 1986 if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
- 1987 return $this->_montgomeryMultiply($x, $y, $n);
- 1988 }
- 1989 $temp = $this->_multiply($x, false, $y, false);
- 1990 return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n, $mode);
- 1991 }
- 1992
- 1993
- 1994
- 1995
- 1996
- 1997
- 1998
- 1999
- 2000
- 2001
- 2002
- 2003 function _squareReduce($x, $n, $mode)
- 2004 {
- 2005 if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
- 2006 return $this->_montgomeryMultiply($x, $x, $n);
- 2007 }
- 2008 return $this->_reduce($this->_square($x), $n, $mode);
- 2009 }
- 2010
- 2011
- 2012
- 2013
- 2014
- 2015
- 2016
- 2017
- 2018
- 2019
- 2020
- 2021
- 2022 function _mod2($n)
- 2023 {
- 2024 $temp = new Math_BigInteger();
- 2025 $temp->value = array(1);
- 2026 return $this->bitwise_and($n->subtract($temp));
- 2027 }
- 2028
- 2029
- 2030
- 2031
- 2032
- 2033
- 2034
- 2035
- 2036
- 2037
- 2038
- 2039
- 2040
- 2041
- 2042
- 2043
- 2044
- 2045
- 2046
- 2047
- 2048
- 2049
- 2050
- 2051
- 2052
- 2053 function _barrett($n, $m)
- 2054 {
- 2055 static $cache = array(
- 2056 MATH_BIGINTEGER_VARIABLE => array(),
- 2057 MATH_BIGINTEGER_DATA => array()
- 2058 );
- 2059
- 2060 $m_length = count($m);
- 2061
- 2062
- 2063 if (count($n) > 2 * $m_length) {
- 2064 $lhs = new Math_BigInteger();
- 2065 $rhs = new Math_BigInteger();
- 2066 $lhs->value = $n;
- 2067 $rhs->value = $m;
- 2068 list(, $temp) = $lhs->divide($rhs);
- 2069 return $temp->value;
- 2070 }
- 2071
- 2072
- 2073 if ($m_length < 5) {
- 2074 return $this->_regularBarrett($n, $m);
- 2075 }
- 2076
- 2077
- 2078
- 2079 if (($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
- 2080 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
- 2081 $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
- 2082
- 2083 $lhs = new Math_BigInteger();
- 2084 $lhs_value = &$lhs->value;
- 2085 $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
- 2086 $lhs_value[] = 1;
- 2087 $rhs = new Math_BigInteger();
- 2088 $rhs->value = $m;
- 2089
- 2090 list($u, $m1) = $lhs->divide($rhs);
- 2091 $u = $u->value;
- 2092 $m1 = $m1->value;
- 2093
- 2094 $cache[MATH_BIGINTEGER_DATA][] = array(
- 2095 'u' => $u,
- 2096 'm1'=> $m1
- 2097 );
- 2098 } else {
- 2099 extract($cache[MATH_BIGINTEGER_DATA][$key]);
- 2100 }
- 2101
- 2102 $cutoff = $m_length + ($m_length >> 1);
- 2103 $lsd = array_slice($n, 0, $cutoff);
- 2104 $msd = array_slice($n, $cutoff);
- 2105 $lsd = $this->_trim($lsd);
- 2106 $temp = $this->_multiply($msd, false, $m1, false);
- 2107 $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE], false);
- 2108
- 2109 if ($m_length & 1) {
- 2110 return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m);
- 2111 }
- 2112
- 2113
- 2114 $temp = array_slice($n[MATH_BIGINTEGER_VALUE], $m_length - 1);
- 2115
- 2116
- 2117 $temp = $this->_multiply($temp, false, $u, false);
- 2118
- 2119
- 2120 $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1);
- 2121
- 2122
- 2123 $temp = $this->_multiply($temp, false, $m, false);
- 2124
- 2125
- 2126
- 2127
- 2128
- 2129 $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
- 2130
- 2131 while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false) >= 0) {
- 2132 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false);
- 2133 }
- 2134
- 2135 return $result[MATH_BIGINTEGER_VALUE];
- 2136 }
- 2137
- 2138
- 2139
- 2140
- 2141
- 2142
- 2143
- 2144
- 2145
- 2146
- 2147
- 2148
- 2149
- 2150 function _regularBarrett($x, $n)
- 2151 {
- 2152 static $cache = array(
- 2153 MATH_BIGINTEGER_VARIABLE => array(),
- 2154 MATH_BIGINTEGER_DATA => array()
- 2155 );
- 2156
- 2157 $n_length = count($n);
- 2158
- 2159 if (count($x) > 2 * $n_length) {
- 2160 $lhs = new Math_BigInteger();
- 2161 $rhs = new Math_BigInteger();
- 2162 $lhs->value = $x;
- 2163 $rhs->value = $n;
- 2164 list(, $temp) = $lhs->divide($rhs);
- 2165 return $temp->value;
- 2166 }
- 2167
- 2168 if (($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
- 2169 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
- 2170 $cache[MATH_BIGINTEGER_VARIABLE][] = $n;
- 2171 $lhs = new Math_BigInteger();
- 2172 $lhs_value = &$lhs->value;
- 2173 $lhs_value = $this->_array_repeat(0, 2 * $n_length);
- 2174 $lhs_value[] = 1;
- 2175 $rhs = new Math_BigInteger();
- 2176 $rhs->value = $n;
- 2177 list($temp, ) = $lhs->divide($rhs);
- 2178 $cache[MATH_BIGINTEGER_DATA][] = $temp->value;
- 2179 }
- 2180
- 2181
- 2182 $temp = array_slice($x, $n_length - 1);
- 2183
- 2184 $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA][$key], false);
- 2185
- 2186 $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length + 1);
- 2187
- 2188
- 2189 $result = array_slice($x, 0, $n_length + 1);
- 2190
- 2191 $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
- 2192
- 2193
- 2194 if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) {
- 2195 $corrector_value = $this->_array_repeat(0, $n_length + 1);
- 2196 $corrector_value[count($corrector_value)] = 1;
- 2197 $result = $this->_add($result, false, $corrector_value, false);
- 2198 $result = $result[MATH_BIGINTEGER_VALUE];
- 2199 }
- 2200
- 2201
- 2202 $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]);
- 2203 while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false) > 0) {
- 2204 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false);
- 2205 }
- 2206
- 2207 return $result[MATH_BIGINTEGER_VALUE];
- 2208 }
- 2209
- 2210
- 2211
- 2212
- 2213
- 2214
- 2215
- 2216
- 2217
- 2218
- 2219
- 2220
- 2221
- 2222
- 2223
- 2224 function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
- 2225 {
- 2226 $x_length = count($x_value);
- 2227 $y_length = count($y_value);
- 2228
- 2229 if (!$x_length || !$y_length) {
- 2230 return array(
- 2231 MATH_BIGINTEGER_VALUE => array(),
- 2232 MATH_BIGINTEGER_SIGN => false
- 2233 );
- 2234 }
- 2235
- 2236 if ($x_length < $y_length) {
- 2237 $temp = $x_value;
- 2238 $x_value = $y_value;
- 2239 $y_value = $temp;
- 2240
- 2241 $x_length = count($x_value);
- 2242 $y_length = count($y_value);
- 2243 }
- 2244
- 2245 $product_value = $this->_array_repeat(0, $x_length + $y_length);
- 2246
- 2247
- 2248
- 2249
- 2250
- 2251
- 2252
- 2253 $carry = 0;
- 2254
- 2255 for ($j = 0; $j < $x_length; ++$j) {
- 2256 $temp = $x_value[$j] * $y_value[0] + $carry;
- 2257 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 2258 $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
- 2259 }
- 2260
- 2261 if ($j < $stop) {
- 2262 $product_value[$j] = $carry;
- 2263 }
- 2264
- 2265
- 2266
- 2267
- 2268 for ($i = 1; $i < $y_length; ++$i) {
- 2269 $carry = 0;
- 2270
- 2271 for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
- 2272 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
- 2273 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 2274 $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
- 2275 }
- 2276
- 2277 if ($k < $stop) {
- 2278 $product_value[$k] = $carry;
- 2279 }
- 2280 }
- 2281
- 2282 return array(
- 2283 MATH_BIGINTEGER_VALUE => $this->_trim($product_value),
- 2284 MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
- 2285 );
- 2286 }
- 2287
- 2288
- 2289
- 2290
- 2291
- 2292
- 2293
- 2294
- 2295
- 2296
- 2297
- 2298
- 2299
- 2300
- 2301
- 2302
- 2303 function _montgomery($x, $n)
- 2304 {
- 2305 static $cache = array(
- 2306 MATH_BIGINTEGER_VARIABLE => array(),
- 2307 MATH_BIGINTEGER_DATA => array()
- 2308 );
- 2309
- 2310 if (($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
- 2311 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
- 2312 $cache[MATH_BIGINTEGER_VARIABLE][] = $x;
- 2313 $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n);
- 2314 }
- 2315
- 2316 $k = count($n);
- 2317
- 2318 $result = array(MATH_BIGINTEGER_VALUE => $x);
- 2319
- 2320 for ($i = 0; $i < $k; ++$i) {
- 2321 $temp = $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key];
- 2322 $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
- 2323 $temp = $this->_regularMultiply(array($temp), $n);
- 2324 $temp = array_merge($this->_array_repeat(0, $i), $temp);
- 2325 $result = $this->_add($result[MATH_BIGINTEGER_VALUE], false, $temp, false);
- 2326 }
- 2327
- 2328 $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k);
- 2329
- 2330 if ($this->_compare($result, false, $n, false) >= 0) {
- 2331 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], false, $n, false);
- 2332 }
- 2333
- 2334 return $result[MATH_BIGINTEGER_VALUE];
- 2335 }
- 2336
- 2337
- 2338
- 2339
- 2340
- 2341
- 2342
- 2343
- 2344
- 2345
- 2346
- 2347
- 2348
- 2349
- 2350
- 2351 function _montgomeryMultiply($x, $y, $m)
- 2352 {
- 2353 $temp = $this->_multiply($x, false, $y, false);
- 2354 return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m);
- 2355
- 2356
- 2357
- 2358
- 2359
- 2360
- 2361 static $cache = array(
- 2362 MATH_BIGINTEGER_VARIABLE => array(),
- 2363 MATH_BIGINTEGER_DATA => array()
- 2364 );
- 2365
- 2366 if (($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
- 2367 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
- 2368 $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
- 2369 $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m);
- 2370 }
- 2371
- 2372 $n = max(count($x), count($y), count($m));
- 2373 $x = array_pad($x, $n, 0);
- 2374 $y = array_pad($y, $n, 0);
- 2375 $m = array_pad($m, $n, 0);
- 2376 $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0, $n + 1));
- 2377 for ($i = 0; $i < $n; ++$i) {
- 2378 $temp = $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0];
- 2379 $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
- 2380 $temp = $temp * $cache[MATH_BIGINTEGER_DATA][$key];
- 2381 $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
- 2382 $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
- 2383 $a = $this->_add($a[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
- 2384 $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1);
- 2385 }
- 2386 if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false, $m, false) >= 0) {
- 2387 $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE], false, $m, false);
- 2388 }
- 2389 return $a[MATH_BIGINTEGER_VALUE];
- 2390 }
- 2391
- 2392
- 2393
- 2394
- 2395
- 2396
- 2397
- 2398
- 2399
- 2400
- 2401
- 2402 function _prepMontgomery($x, $n)
- 2403 {
- 2404 $lhs = new Math_BigInteger();
- 2405 $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
- 2406 $rhs = new Math_BigInteger();
- 2407 $rhs->value = $n;
- 2408
- 2409 list(, $temp) = $lhs->divide($rhs);
- 2410 return $temp->value;
- 2411 }
- 2412
- 2413
- 2414
- 2415
- 2416
- 2417
- 2418
- 2419
- 2420
- 2421
- 2422
- 2423
- 2424
- 2425
- 2426
- 2427
- 2428
- 2429
- 2430
- 2431
- 2432
- 2433
- 2434
- 2435
- 2436
- 2437
- 2438
- 2439 function _modInverse67108864($x)
- 2440 {
- 2441 $x = -$x[0];
- 2442 $result = $x & 0x3;
- 2443 $result = ($result * (2 - $x * $result)) & 0xF;
- 2444 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF;
- 2445 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF;
- 2446 $result = fmod($result * (2 - fmod($x * $result, MATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL);
- 2447 return $result & MATH_BIGINTEGER_MAX_DIGIT;
- 2448 }
- 2449
- 2450
- 2451
- 2452
- 2453
- 2454
- 2455
- 2456
- 2457
- 2458
- 2459
- 2460
- 2461
- 2462
- 2463
- 2464
- 2465
- 2466
- 2467
- 2468
- 2469
- 2470
- 2471
- 2472
- 2473
- 2474
- 2475
- 2476
- 2477
- 2478
- 2479 function modInverse($n)
- 2480 {
- 2481 switch (MATH_BIGINTEGER_MODE) {
- 2482 case MATH_BIGINTEGER_MODE_GMP:
- 2483 $temp = new Math_BigInteger();
- 2484 $temp->value = gmp_invert($this->value, $n->value);
- 2485
- 2486 return ($temp->value === false) ? false : $this->_normalize($temp);
- 2487 }
- 2488
- 2489 static $zero, $one;
- 2490 if (!isset($zero)) {
- 2491 $zero = new Math_BigInteger();
- 2492 $one = new Math_BigInteger(1);
- 2493 }
- 2494
- 2495
- 2496 $n = $n->abs();
- 2497
- 2498 if ($this->compare($zero) < 0) {
- 2499 $temp = $this->abs();
- 2500 $temp = $temp->modInverse($n);
- 2501 return $this->_normalize($n->subtract($temp));
- 2502 }
- 2503
- 2504 extract($this->extendedGCD($n));
- 2505
- 2506 if (!$gcd->equals($one)) {
- 2507 return false;
- 2508 }
- 2509
- 2510 $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
- 2511
- 2512 return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
- 2513 }
- 2514
- 2515
- 2516
- 2517
- 2518
- 2519
- 2520
- 2521
- 2522
- 2523
- 2524
- 2525
- 2526
- 2527
- 2528
- 2529
- 2530
- 2531
- 2532
- 2533
- 2534
- 2535
- 2536
- 2537
- 2538
- 2539
- 2540
- 2541
- 2542
- 2543
- 2544
- 2545 function extendedGCD($n)
- 2546 {
- 2547 switch (MATH_BIGINTEGER_MODE) {
- 2548 case MATH_BIGINTEGER_MODE_GMP:
- 2549 extract(gmp_gcdext($this->value, $n->value));
- 2550
- 2551 return array(
- 2552 'gcd' => $this->_normalize(new Math_BigInteger($g)),
- 2553 'x' => $this->_normalize(new Math_BigInteger($s)),
- 2554 'y' => $this->_normalize(new Math_BigInteger($t))
- 2555 );
- 2556 case MATH_BIGINTEGER_MODE_BCMATH:
- 2557
- 2558
- 2559
- 2560
- 2561 $u = $this->value;
- 2562 $v = $n->value;
- 2563
- 2564 $a = '1';
- 2565 $b = '0';
- 2566 $c = '0';
- 2567 $d = '1';
- 2568
- 2569 while (bccomp($v, '0', 0) != 0) {
- 2570 $q = bcdiv($u, $v, 0);
- 2571
- 2572 $temp = $u;
- 2573 $u = $v;
- 2574 $v = bcsub($temp, bcmul($v, $q, 0), 0);
- 2575
- 2576 $temp = $a;
- 2577 $a = $c;
- 2578 $c = bcsub($temp, bcmul($a, $q, 0), 0);
- 2579
- 2580 $temp = $b;
- 2581 $b = $d;
- 2582 $d = bcsub($temp, bcmul($b, $q, 0), 0);
- 2583 }
- 2584
- 2585 return array(
- 2586 'gcd' => $this->_normalize(new Math_BigInteger($u)),
- 2587 'x' => $this->_normalize(new Math_BigInteger($a)),
- 2588 'y' => $this->_normalize(new Math_BigInteger($b))
- 2589 );
- 2590 }
- 2591
- 2592 $y = $n->copy();
- 2593 $x = $this->copy();
- 2594 $g = new Math_BigInteger();
- 2595 $g->value = array(1);
- 2596
- 2597 while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
- 2598 $x->_rshift(1);
- 2599 $y->_rshift(1);
- 2600 $g->_lshift(1);
- 2601 }
- 2602
- 2603 $u = $x->copy();
- 2604 $v = $y->copy();
- 2605
- 2606 $a = new Math_BigInteger();
- 2607 $b = new Math_BigInteger();
- 2608 $c = new Math_BigInteger();
- 2609 $d = new Math_BigInteger();
- 2610
- 2611 $a->value = $d->value = $g->value = array(1);
- 2612 $b->value = $c->value = array();
- 2613
- 2614 while (!empty($u->value)) {
- 2615 while (!($u->value[0] & 1)) {
- 2616 $u->_rshift(1);
- 2617 if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
- 2618 $a = $a->add($y);
- 2619 $b = $b->subtract($x);
- 2620 }
- 2621 $a->_rshift(1);
- 2622 $b->_rshift(1);
- 2623 }
- 2624
- 2625 while (!($v->value[0] & 1)) {
- 2626 $v->_rshift(1);
- 2627 if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
- 2628 $c = $c->add($y);
- 2629 $d = $d->subtract($x);
- 2630 }
- 2631 $c->_rshift(1);
- 2632 $d->_rshift(1);
- 2633 }
- 2634
- 2635 if ($u->compare($v) >= 0) {
- 2636 $u = $u->subtract($v);
- 2637 $a = $a->subtract($c);
- 2638 $b = $b->subtract($d);
- 2639 } else {
- 2640 $v = $v->subtract($u);
- 2641 $c = $c->subtract($a);
- 2642 $d = $d->subtract($b);
- 2643 }
- 2644 }
- 2645
- 2646 return array(
- 2647 'gcd' => $this->_normalize($g->multiply($v)),
- 2648 'x' => $this->_normalize($c),
- 2649 'y' => $this->_normalize($d)
- 2650 );
- 2651 }
- 2652
- 2653
- 2654
- 2655
- 2656
- 2657
- 2658
- 2659
- 2660
- 2661
- 2662
- 2663
- 2664
- 2665
- 2666
- 2667
- 2668
- 2669
- 2670
- 2671
- 2672
- 2673
- 2674
- 2675
- 2676 function gcd($n)
- 2677 {
- 2678 extract($this->extendedGCD($n));
- 2679 return $gcd;
- 2680 }
- 2681
- 2682
- 2683
- 2684
- 2685
- 2686
- 2687
- 2688 function abs()
- 2689 {
- 2690 $temp = new Math_BigInteger();
- 2691
- 2692 switch (MATH_BIGINTEGER_MODE) {
- 2693 case MATH_BIGINTEGER_MODE_GMP:
- 2694 $temp->value = gmp_abs($this->value);
- 2695 break;
- 2696 case MATH_BIGINTEGER_MODE_BCMATH:
- 2697 $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
- 2698 break;
- 2699 default:
- 2700 $temp->value = $this->value;
- 2701 }
- 2702
- 2703 return $temp;
- 2704 }
- 2705
- 2706
- 2707
- 2708
- 2709
- 2710
- 2711
- 2712
- 2713
- 2714
- 2715
- 2716
- 2717
- 2718
- 2719
- 2720
- 2721
- 2722
- 2723
- 2724 function compare($y)
- 2725 {
- 2726 switch (MATH_BIGINTEGER_MODE) {
- 2727 case MATH_BIGINTEGER_MODE_GMP:
- 2728 return gmp_cmp($this->value, $y->value);
- 2729 case MATH_BIGINTEGER_MODE_BCMATH:
- 2730 return bccomp($this->value, $y->value, 0);
- 2731 }
- 2732
- 2733 return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
- 2734 }
- 2735
- 2736
- 2737
- 2738
- 2739
- 2740
- 2741
- 2742
- 2743
- 2744
- 2745
- 2746
- 2747 function _compare($x_value, $x_negative, $y_value, $y_negative)
- 2748 {
- 2749 if ($x_negative != $y_negative) {
- 2750 return (!$x_negative && $y_negative) ? 1 : -1;
- 2751 }
- 2752
- 2753 $result = $x_negative ? -1 : 1;
- 2754
- 2755 if (count($x_value) != count($y_value)) {
- 2756 return (count($x_value) > count($y_value)) ? $result : -$result;
- 2757 }
- 2758 $size = max(count($x_value), count($y_value));
- 2759
- 2760 $x_value = array_pad($x_value, $size, 0);
- 2761 $y_value = array_pad($y_value, $size, 0);
- 2762
- 2763 for ($i = count($x_value) - 1; $i >= 0; --$i) {
- 2764 if ($x_value[$i] != $y_value[$i]) {
- 2765 return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
- 2766 }
- 2767 }
- 2768
- 2769 return 0;
- 2770 }
- 2771
- 2772
- 2773
- 2774
- 2775
- 2776
- 2777
- 2778
- 2779
- 2780
- 2781
- 2782 function equals($x)
- 2783 {
- 2784 switch (MATH_BIGINTEGER_MODE) {
- 2785 case MATH_BIGINTEGER_MODE_GMP:
- 2786 return gmp_cmp($this->value, $x->value) == 0;
- 2787 default:
- 2788 return $this->value === $x->value && $this->is_negative == $x->is_negative;
- 2789 }
- 2790 }
- 2791
- 2792
- 2793
- 2794
- 2795
- 2796
- 2797
- 2798
- 2799
- 2800
- 2801 function setPrecision($bits)
- 2802 {
- 2803 $this->precision = $bits;
- 2804 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH) {
- 2805 $this->bitmask = new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
- 2806 } else {
- 2807 $this->bitmask = new Math_BigInteger(bcpow('2', $bits, 0));
- 2808 }
- 2809
- 2810 $temp = $this->_normalize($this);
- 2811 $this->value = $temp->value;
- 2812 }
- 2813
- 2814
- 2815
- 2816
- 2817
- 2818
- 2819
- 2820
- 2821
- 2822 function bitwise_and($x)
- 2823 {
- 2824 switch (MATH_BIGINTEGER_MODE) {
- 2825 case MATH_BIGINTEGER_MODE_GMP:
- 2826 $temp = new Math_BigInteger();
- 2827 $temp->value = gmp_and($this->value, $x->value);
- 2828
- 2829 return $this->_normalize($temp);
- 2830 case MATH_BIGINTEGER_MODE_BCMATH:
- 2831 $left = $this->toBytes();
- 2832 $right = $x->toBytes();
- 2833
- 2834 $length = max(strlen($left), strlen($right));
- 2835
- 2836 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
- 2837 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
- 2838
- 2839 return $this->_normalize(new Math_BigInteger($left & $right, 256));
- 2840 }
- 2841
- 2842 $result = $this->copy();
- 2843
- 2844 $length = min(count($x->value), count($this->value));
- 2845
- 2846 $result->value = array_slice($result->value, 0, $length);
- 2847
- 2848 for ($i = 0; $i < $length; ++$i) {
- 2849 $result->value[$i]&= $x->value[$i];
- 2850 }
- 2851
- 2852 return $this->_normalize($result);
- 2853 }
- 2854
- 2855
- 2856
- 2857
- 2858
- 2859
- 2860
- 2861
- 2862
- 2863 function bitwise_or($x)
- 2864 {
- 2865 switch (MATH_BIGINTEGER_MODE) {
- 2866 case MATH_BIGINTEGER_MODE_GMP:
- 2867 $temp = new Math_BigInteger();
- 2868 $temp->value = gmp_or($this->value, $x->value);
- 2869
- 2870 return $this->_normalize($temp);
- 2871 case MATH_BIGINTEGER_MODE_BCMATH:
- 2872 $left = $this->toBytes();
- 2873 $right = $x->toBytes();
- 2874
- 2875 $length = max(strlen($left), strlen($right));
- 2876
- 2877 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
- 2878 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
- 2879
- 2880 return $this->_normalize(new Math_BigInteger($left | $right, 256));
- 2881 }
- 2882
- 2883 $length = max(count($this->value), count($x->value));
- 2884 $result = $this->copy();
- 2885 $result->value = array_pad($result->value, $length, 0);
- 2886 $x->value = array_pad($x->value, $length, 0);
- 2887
- 2888 for ($i = 0; $i < $length; ++$i) {
- 2889 $result->value[$i]|= $x->value[$i];
- 2890 }
- 2891
- 2892 return $this->_normalize($result);
- 2893 }
- 2894
- 2895
- 2896
- 2897
- 2898
- 2899
- 2900
- 2901
- 2902
- 2903 function bitwise_xor($x)
- 2904 {
- 2905 switch (MATH_BIGINTEGER_MODE) {
- 2906 case MATH_BIGINTEGER_MODE_GMP:
- 2907 $temp = new Math_BigInteger();
- 2908 $temp->value = gmp_xor(gmp_abs($this->value), gmp_abs($x->value));
- 2909
- 2910 return $this->_normalize($temp);
- 2911 case MATH_BIGINTEGER_MODE_BCMATH:
- 2912 $left = $this->toBytes();
- 2913 $right = $x->toBytes();
- 2914
- 2915 $length = max(strlen($left), strlen($right));
- 2916
- 2917 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
- 2918 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
- 2919
- 2920 return $this->_normalize(new Math_BigInteger($left ^ $right, 256));
- 2921 }
- 2922
- 2923 $length = max(count($this->value), count($x->value));
- 2924 $result = $this->copy();
- 2925 $result->is_negative = false;
- 2926 $result->value = array_pad($result->value, $length, 0);
- 2927 $x->value = array_pad($x->value, $length, 0);
- 2928
- 2929 for ($i = 0; $i < $length; ++$i) {
- 2930 $result->value[$i]^= $x->value[$i];
- 2931 }
- 2932
- 2933 return $this->_normalize($result);
- 2934 }
- 2935
- 2936
- 2937
- 2938
- 2939
- 2940
- 2941
- 2942
- 2943 function bitwise_not()
- 2944 {
- 2945
- 2946
- 2947 $temp = $this->toBytes();
- 2948 if ($temp == '') {
- 2949 return $this->_normalize(new Math_BigInteger());
- 2950 }
- 2951 $pre_msb = decbin(ord($temp[0]));
- 2952 $temp = ~$temp;
- 2953 $msb = decbin(ord($temp[0]));
- 2954 if (strlen($msb) == 8) {
- 2955 $msb = substr($msb, strpos($msb, '0'));
- 2956 }
- 2957 $temp[0] = chr(bindec($msb));
- 2958
- 2959
- 2960 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
- 2961 $new_bits = $this->precision - $current_bits;
- 2962 if ($new_bits <= 0) {
- 2963 return $this->_normalize(new Math_BigInteger($temp, 256));
- 2964 }
- 2965
- 2966
- 2967 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
- 2968 $this->_base256_lshift($leading_ones, $current_bits);
- 2969
- 2970 $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
- 2971
- 2972 return $this->_normalize(new Math_BigInteger($leading_ones | $temp, 256));
- 2973 }
- 2974
- 2975
- 2976
- 2977
- 2978
- 2979
- 2980
- 2981
- 2982
- 2983
- 2984
- 2985 function bitwise_rightShift($shift)
- 2986 {
- 2987 $temp = new Math_BigInteger();
- 2988
- 2989 switch (MATH_BIGINTEGER_MODE) {
- 2990 case MATH_BIGINTEGER_MODE_GMP:
- 2991 static $two;
- 2992
- 2993 if (!isset($two)) {
- 2994 $two = gmp_init('2');
- 2995 }
- 2996
- 2997 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
- 2998
- 2999 break;
- 3000 case MATH_BIGINTEGER_MODE_BCMATH:
- 3001 $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
- 3002
- 3003 break;
- 3004 default:
- 3005
- 3006 $temp->value = $this->value;
- 3007 $temp->_rshift($shift);
- 3008 }
- 3009
- 3010 return $this->_normalize($temp);
- 3011 }
- 3012
- 3013
- 3014
- 3015
- 3016
- 3017
- 3018
- 3019
- 3020
- 3021
- 3022
- 3023 function bitwise_leftShift($shift)
- 3024 {
- 3025 $temp = new Math_BigInteger();
- 3026
- 3027 switch (MATH_BIGINTEGER_MODE) {
- 3028 case MATH_BIGINTEGER_MODE_GMP:
- 3029 static $two;
- 3030
- 3031 if (!isset($two)) {
- 3032 $two = gmp_init('2');
- 3033 }
- 3034
- 3035 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
- 3036
- 3037 break;
- 3038 case MATH_BIGINTEGER_MODE_BCMATH:
- 3039 $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
- 3040
- 3041 break;
- 3042 default:
- 3043
- 3044 $temp->value = $this->value;
- 3045 $temp->_lshift($shift);
- 3046 }
- 3047
- 3048 return $this->_normalize($temp);
- 3049 }
- 3050
- 3051
- 3052
- 3053
- 3054
- 3055
- 3056
- 3057
- 3058
- 3059
- 3060 function bitwise_leftRotate($shift)
- 3061 {
- 3062 $bits = $this->toBytes();
- 3063
- 3064 if ($this->precision > 0) {
- 3065 $precision = $this->precision;
- 3066 if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
- 3067 $mask = $this->bitmask->subtract(new Math_BigInteger(1));
- 3068 $mask = $mask->toBytes();
- 3069 } else {
- 3070 $mask = $this->bitmask->toBytes();
- 3071 }
- 3072 } else {
- 3073 $temp = ord($bits[0]);
- 3074 for ($i = 0; $temp >> $i; ++$i) {
- 3075 }
- 3076 $precision = 8 * strlen($bits) - 8 + $i;
- 3077 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
- 3078 }
- 3079
- 3080 if ($shift < 0) {
- 3081 $shift+= $precision;
- 3082 }
- 3083 $shift%= $precision;
- 3084
- 3085 if (!$shift) {
- 3086 return $this->copy();
- 3087 }
- 3088
- 3089 $left = $this->bitwise_leftShift($shift);
- 3090 $left = $left->bitwise_and(new Math_BigInteger($mask, 256));
- 3091 $right = $this->bitwise_rightShift($precision - $shift);
- 3092 $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
- 3093 return $this->_normalize($result);
- 3094 }
- 3095
- 3096
- 3097
- 3098
- 3099
- 3100
- 3101
- 3102
- 3103
- 3104
- 3105 function bitwise_rightRotate($shift)
- 3106 {
- 3107 return $this->bitwise_leftRotate(-$shift);
- 3108 }
- 3109
- 3110
- 3111
- 3112
- 3113
- 3114
- 3115
- 3116
- 3117
- 3118 function setRandomGenerator($generator)
- 3119 {
- 3120 }
- 3121
- 3122
- 3123
- 3124
- 3125
- 3126
- 3127
- 3128
- 3129
- 3130
- 3131 function _random_number_helper($size)
- 3132 {
- 3133 if (function_exists('crypt_random_string')) {
- 3134 $random = crypt_random_string($size);
- 3135 } else {
- 3136 $random = '';
- 3137
- 3138 if ($size & 1) {
- 3139 $random.= chr(mt_rand(0, 255));
- 3140 }
- 3141
- 3142 $blocks = $size >> 1;
- 3143 for ($i = 0; $i < $blocks; ++$i) {
- 3144
- 3145 $random.= pack('n', mt_rand(0, 0xFFFF));
- 3146 }
- 3147 }
- 3148
- 3149 return new Math_BigInteger($random, 256);
- 3150 }
- 3151
- 3152
- 3153
- 3154
- 3155
- 3156
- 3157
- 3158
- 3159
- 3160
- 3161
- 3162
- 3163
- 3164
- 3165
- 3166
- 3167
- 3168 function random($arg1, $arg2 = false)
- 3169 {
- 3170 if ($arg1 === false) {
- 3171 return false;
- 3172 }
- 3173
- 3174 if ($arg2 === false) {
- 3175 $max = $arg1;
- 3176 $min = $this;
- 3177 } else {
- 3178 $min = $arg1;
- 3179 $max = $arg2;
- 3180 }
- 3181
- 3182 $compare = $max->compare($min);
- 3183
- 3184 if (!$compare) {
- 3185 return $this->_normalize($min);
- 3186 } elseif ($compare < 0) {
- 3187
- 3188 $temp = $max;
- 3189 $max = $min;
- 3190 $min = $temp;
- 3191 }
- 3192
- 3193 static $one;
- 3194 if (!isset($one)) {
- 3195 $one = new Math_BigInteger(1);
- 3196 }
- 3197
- 3198 $max = $max->subtract($min->subtract($one));
- 3199 $size = strlen(ltrim($max->toBytes(), chr(0)));
- 3200
- 3201
- 3202
- 3203
- 3204
- 3205
- 3206
- 3207
- 3208
- 3209
- 3210
- 3211
- 3212
- 3213
- 3214
- 3215
- 3216 $random_max = new Math_BigInteger(chr(1) . str_repeat("\0", $size), 256);
- 3217 $random = $this->_random_number_helper($size);
- 3218
- 3219 list($max_multiple) = $random_max->divide($max);
- 3220 $max_multiple = $max_multiple->multiply($max);
- 3221
- 3222 while ($random->compare($max_multiple) >= 0) {
- 3223 $random = $random->subtract($max_multiple);
- 3224 $random_max = $random_max->subtract($max_multiple);
- 3225 $random = $random->bitwise_leftShift(8);
- 3226 $random = $random->add($this->_random_number_helper(1));
- 3227 $random_max = $random_max->bitwise_leftShift(8);
- 3228 list($max_multiple) = $random_max->divide($max);
- 3229 $max_multiple = $max_multiple->multiply($max);
- 3230 }
- 3231 list(, $random) = $random->divide($max);
- 3232
- 3233 return $this->_normalize($random->add($min));
- 3234 }
- 3235
- 3236
- 3237
- 3238
- 3239
- 3240
- 3241
- 3242
- 3243
- 3244
- 3245
- 3246
- 3247
- 3248
- 3249 function randomPrime($arg1, $arg2 = false, $timeout = false)
- 3250 {
- 3251 if ($arg1 === false) {
- 3252 return false;
- 3253 }
- 3254
- 3255 if ($arg2 === false) {
- 3256 $max = $arg1;
- 3257 $min = $this;
- 3258 } else {
- 3259 $min = $arg1;
- 3260 $max = $arg2;
- 3261 }
- 3262
- 3263 $compare = $max->compare($min);
- 3264
- 3265 if (!$compare) {
- 3266 return $min->isPrime() ? $min : false;
- 3267 } elseif ($compare < 0) {
- 3268
- 3269 $temp = $max;
- 3270 $max = $min;
- 3271 $min = $temp;
- 3272 }
- 3273
- 3274 static $one, $two;
- 3275 if (!isset($one)) {
- 3276 $one = new Math_BigInteger(1);
- 3277 $two = new Math_BigInteger(2);
- 3278 }
- 3279
- 3280 $start = time();
- 3281
- 3282 $x = $this->random($min, $max);
- 3283
- 3284
- 3285 if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && extension_loaded('gmp') && version_compare(PHP_VERSION, '5.2.0', '>=')) {
- 3286 $p = new Math_BigInteger();
- 3287 $p->value = gmp_nextprime($x->value);
- 3288
- 3289 if ($p->compare($max) <= 0) {
- 3290 return $p;
- 3291 }
- 3292
- 3293 if (!$min->equals($x)) {
- 3294 $x = $x->subtract($one);
- 3295 }
- 3296
- 3297 return $x->randomPrime($min, $x);
- 3298 }
- 3299
- 3300 if ($x->equals($two)) {
- 3301 return $x;
- 3302 }
- 3303
- 3304 $x->_make_odd();
- 3305 if ($x->compare($max) > 0) {
- 3306
- 3307 if ($min->equals($max)) {
- 3308 return false;
- 3309 }
- 3310 $x = $min->copy();
- 3311 $x->_make_odd();
- 3312 }
- 3313
- 3314 $initial_x = $x->copy();
- 3315
- 3316 while (true) {
- 3317 if ($timeout !== false && time() - $start > $timeout) {
- 3318 return false;
- 3319 }
- 3320
- 3321 if ($x->isPrime()) {
- 3322 return $x;
- 3323 }
- 3324
- 3325 $x = $x->add($two);
- 3326
- 3327 if ($x->compare($max) > 0) {
- 3328 $x = $min->copy();
- 3329 if ($x->equals($two)) {
- 3330 return $x;
- 3331 }
- 3332 $x->_make_odd();
- 3333 }
- 3334
- 3335 if ($x->equals($initial_x)) {
- 3336 return false;
- 3337 }
- 3338 }
- 3339 }
- 3340
- 3341
- 3342
- 3343
- 3344
- 3345
- 3346
- 3347
- 3348
- 3349 function _make_odd()
- 3350 {
- 3351 switch (MATH_BIGINTEGER_MODE) {
- 3352 case MATH_BIGINTEGER_MODE_GMP:
- 3353 gmp_setbit($this->value, 0);
- 3354 break;
- 3355 case MATH_BIGINTEGER_MODE_BCMATH:
- 3356 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
- 3357 $this->value = bcadd($this->value, '1');
- 3358 }
- 3359 break;
- 3360 default:
- 3361 $this->value[0] |= 1;
- 3362 }
- 3363 }
- 3364
- 3365
- 3366
- 3367
- 3368
- 3369
- 3370
- 3371
- 3372
- 3373
- 3374
- 3375
- 3376
- 3377
- 3378
- 3379 function isPrime($t = false)
- 3380 {
- 3381 $length = strlen($this->toBytes());
- 3382
- 3383 if (!$t) {
- 3384
- 3385
- 3386 if ($length >= 163) { $t = 2; }
- 3387 else if ($length >= 106) { $t = 3; }
- 3388 else if ($length >= 81 ) { $t = 4; }
- 3389 else if ($length >= 68 ) { $t = 5; }
- 3390 else if ($length >= 56 ) { $t = 6; }
- 3391 else if ($length >= 50 ) { $t = 7; }
- 3392 else if ($length >= 43 ) { $t = 8; }
- 3393 else if ($length >= 37 ) { $t = 9; }
- 3394 else if ($length >= 31 ) { $t = 12; }
- 3395 else if ($length >= 25 ) { $t = 15; }
- 3396 else if ($length >= 18 ) { $t = 18; }
- 3397 else { $t = 27; }
- 3398
- 3399 }
- 3400
- 3401
- 3402
- 3403 switch (MATH_BIGINTEGER_MODE) {
- 3404 case MATH_BIGINTEGER_MODE_GMP:
- 3405 return gmp_prob_prime($this->value, $t) != 0;
- 3406 case MATH_BIGINTEGER_MODE_BCMATH:
- 3407 if ($this->value === '2') {
- 3408 return true;
- 3409 }
- 3410 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
- 3411 return false;
- 3412 }
- 3413 break;
- 3414 default:
- 3415 if ($this->value == array(2)) {
- 3416 return true;
- 3417 }
- 3418 if (~$this->value[0] & 1) {
- 3419 return false;
- 3420 }
- 3421 }
- 3422
- 3423 static $primes, $zero, $one, $two;
- 3424
- 3425 if (!isset($primes)) {
- 3426 $primes = array(
- 3427 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
- 3428 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
- 3429 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
- 3430 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
- 3431 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
- 3432 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
- 3433 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
- 3434 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
- 3435 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
- 3436 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
- 3437 953, 967, 971, 977, 983, 991, 997
- 3438 );
- 3439
- 3440 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
- 3441 for ($i = 0; $i < count($primes); ++$i) {
- 3442 $primes[$i] = new Math_BigInteger($primes[$i]);
- 3443 }
- 3444 }
- 3445
- 3446 $zero = new Math_BigInteger();
- 3447 $one = new Math_BigInteger(1);
- 3448 $two = new Math_BigInteger(2);
- 3449 }
- 3450
- 3451 if ($this->equals($one)) {
- 3452 return false;
- 3453 }
- 3454
- 3455
- 3456 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
- 3457 foreach ($primes as $prime) {
- 3458 list(, $r) = $this->divide($prime);
- 3459 if ($r->equals($zero)) {
- 3460 return $this->equals($prime);
- 3461 }
- 3462 }
- 3463 } else {
- 3464 $value = $this->value;
- 3465 foreach ($primes as $prime) {
- 3466 list(, $r) = $this->_divide_digit($value, $prime);
- 3467 if (!$r) {
- 3468 return count($value) == 1 && $value[0] == $prime;
- 3469 }
- 3470 }
- 3471 }
- 3472
- 3473 $n = $this->copy();
- 3474 $n_1 = $n->subtract($one);
- 3475 $n_2 = $n->subtract($two);
- 3476
- 3477 $r = $n_1->copy();
- 3478 $r_value = $r->value;
- 3479
- 3480 if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
- 3481 $s = 0;
- 3482
- 3483 while ($r->value[strlen($r->value) - 1] % 2 == 0) {
- 3484 $r->value = bcdiv($r->value, '2', 0);
- 3485 ++$s;
- 3486 }
- 3487 } else {
- 3488 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
- 3489 $temp = ~$r_value[$i] & 0xFFFFFF;
- 3490 for ($j = 1; ($temp >> $j) & 1; ++$j) {
- 3491 }
- 3492 if ($j != 25) {
- 3493 break;
- 3494 }
- 3495 }
- 3496 $s = 26 * $i + $j;
- 3497 $r->_rshift($s);
- 3498 }
- 3499
- 3500 for ($i = 0; $i < $t; ++$i) {
- 3501 $a = $this->random($two, $n_2);
- 3502 $y = $a->modPow($r, $n);
- 3503
- 3504 if (!$y->equals($one) && !$y->equals($n_1)) {
- 3505 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
- 3506 $y = $y->modPow($two, $n);
- 3507 if ($y->equals($one)) {
- 3508 return false;
- 3509 }
- 3510 }
- 3511
- 3512 if (!$y->equals($n_1)) {
- 3513 return false;
- 3514 }
- 3515 }
- 3516 }
- 3517 return true;
- 3518 }
- 3519
- 3520
- 3521
- 3522
- 3523
- 3524
- 3525
- 3526
- 3527
- 3528 function _lshift($shift)
- 3529 {
- 3530 if ($shift == 0) {
- 3531 return;
- 3532 }
- 3533
- 3534 $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
- 3535 $shift %= MATH_BIGINTEGER_BASE;
- 3536 $shift = 1 << $shift;
- 3537
- 3538 $carry = 0;
- 3539
- 3540 for ($i = 0; $i < count($this->value); ++$i) {
- 3541 $temp = $this->value[$i] * $shift + $carry;
- 3542 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
- 3543 $this->value[$i] = (int) ($temp - $carry * MATH_BIGINTEGER_BASE_FULL);
- 3544 }
- 3545
- 3546 if ($carry) {
- 3547 $this->value[count($this->value)] = $carry;
- 3548 }
- 3549
- 3550 while ($num_digits--) {
- 3551 array_unshift($this->value, 0);
- 3552 }
- 3553 }
- 3554
- 3555
- 3556
- 3557
- 3558
- 3559
- 3560
- 3561
- 3562
- 3563 function _rshift($shift)
- 3564 {
- 3565 if ($shift == 0) {
- 3566 return;
- 3567 }
- 3568
- 3569 $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
- 3570 $shift %= MATH_BIGINTEGER_BASE;
- 3571 $carry_shift = MATH_BIGINTEGER_BASE - $shift;
- 3572 $carry_mask = (1 << $shift) - 1;
- 3573
- 3574 if ($num_digits) {
- 3575 $this->value = array_slice($this->value, $num_digits);
- 3576 }
- 3577
- 3578 $carry = 0;
- 3579
- 3580 for ($i = count($this->value) - 1; $i >= 0; --$i) {
- 3581 $temp = $this->value[$i] >> $shift | $carry;
- 3582 $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
- 3583 $this->value[$i] = $temp;
- 3584 }
- 3585
- 3586 $this->value = $this->_trim($this->value);
- 3587 }
- 3588
- 3589
- 3590
- 3591
- 3592
- 3593
- 3594
- 3595
- 3596
- 3597
- 3598
- 3599 function _normalize($result)
- 3600 {
- 3601 $result->precision = $this->precision;
- 3602 $result->bitmask = $this->bitmask;
- 3603
- 3604 switch (MATH_BIGINTEGER_MODE) {
- 3605 case MATH_BIGINTEGER_MODE_GMP:
- 3606 if ($this->bitmask !== false) {
- 3607 $result->value = gmp_and($result->value, $result->bitmask->value);
- 3608 }
- 3609
- 3610 return $result;
- 3611 case MATH_BIGINTEGER_MODE_BCMATH:
- 3612 if (!empty($result->bitmask->value)) {
- 3613 $result->value = bcmod($result->value, $result->bitmask->value);
- 3614 }
- 3615
- 3616 return $result;
- 3617 }
- 3618
- 3619 $value = &$result->value;
- 3620
- 3621 if (!count($value)) {
- 3622 return $result;
- 3623 }
- 3624
- 3625 $value = $this->_trim($value);
- 3626
- 3627 if (!empty($result->bitmask->value)) {
- 3628 $length = min(count($value), count($this->bitmask->value));
- 3629 $value = array_slice($value, 0, $length);
- 3630
- 3631 for ($i = 0; $i < $length; ++$i) {
- 3632 $value[$i] = $value[$i] & $this->bitmask->value[$i];
- 3633 }
- 3634 }
- 3635
- 3636 return $result;
- 3637 }
- 3638
- 3639
- 3640
- 3641
- 3642
- 3643
- 3644
- 3645
- 3646
- 3647
- 3648 function _trim($value)
- 3649 {
- 3650 for ($i = count($value) - 1; $i >= 0; --$i) {
- 3651 if ($value[$i]) {
- 3652 break;
- 3653 }
- 3654 unset($value[$i]);
- 3655 }
- 3656
- 3657 return $value;
- 3658 }
- 3659
- 3660
- 3661
- 3662
- 3663
- 3664
- 3665
- 3666
- 3667
- 3668 function _array_repeat($input, $multiplier)
- 3669 {
- 3670 return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
- 3671 }
- 3672
- 3673
- 3674
- 3675
- 3676
- 3677
- 3678
- 3679
- 3680
- 3681
- 3682
- 3683 function _base256_lshift(&$x, $shift)
- 3684 {
- 3685 if ($shift == 0) {
- 3686 return;
- 3687 }
- 3688
- 3689 $num_bytes = $shift >> 3;
- 3690 $shift &= 7;
- 3691
- 3692 $carry = 0;
- 3693 for ($i = strlen($x) - 1; $i >= 0; --$i) {
- 3694 $temp = ord($x[$i]) << $shift | $carry;
- 3695 $x[$i] = chr($temp);
- 3696 $carry = $temp >> 8;
- 3697 }
- 3698 $carry = ($carry != 0) ? chr($carry) : '';
- 3699 $x = $carry . $x . str_repeat(chr(0), $num_bytes);
- 3700 }
- 3701
- 3702
- 3703
- 3704
- 3705
- 3706
- 3707
- 3708
- 3709
- 3710
- 3711
- 3712 function _base256_rshift(&$x, $shift)
- 3713 {
- 3714 if ($shift == 0) {
- 3715 $x = ltrim($x, chr(0));
- 3716 return '';
- 3717 }
- 3718
- 3719 $num_bytes = $shift >> 3;
- 3720 $shift &= 7;
- 3721
- 3722 $remainder = '';
- 3723 if ($num_bytes) {
- 3724 $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
- 3725 $remainder = substr($x, $start);
- 3726 $x = substr($x, 0, -$num_bytes);
- 3727 }
- 3728
- 3729 $carry = 0;
- 3730 $carry_shift = 8 - $shift;
- 3731 for ($i = 0; $i < strlen($x); ++$i) {
- 3732 $temp = (ord($x[$i]) >> $shift) | $carry;
- 3733 $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
- 3734 $x[$i] = chr($temp);
- 3735 }
- 3736 $x = ltrim($x, chr(0));
- 3737
- 3738 $remainder = chr($carry >> $carry_shift) . $remainder;
- 3739
- 3740 return ltrim($remainder, chr(0));
- 3741 }
- 3742
- 3743
- 3744
- 3745
- 3746
- 3747
- 3748
- 3749
- 3750
- 3751
- 3752
- 3753 function _int2bytes($x)
- 3754 {
- 3755 return ltrim(pack('N', $x), chr(0));
- 3756 }
- 3757
- 3758
- 3759
- 3760
- 3761
- 3762
- 3763
- 3764
- 3765 function _bytes2int($x)
- 3766 {
- 3767 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
- 3768 return $temp['int'];
- 3769 }
- 3770
- 3771
- 3772
- 3773
- 3774
- 3775
- 3776
- 3777
- 3778
- 3779
- 3780
- 3781 function _encodeASN1Length($length)
- 3782 {
- 3783 if ($length <= 0x7F) {
- 3784 return chr($length);
- 3785 }
- 3786
- 3787 $temp = ltrim(pack('N', $length), chr(0));
- 3788 return pack('Ca*', 0x80 | strlen($temp), $temp);
- 3789 }
- 3790
- 3791
- 3792
- 3793
- 3794
- 3795
- 3796
- 3797
- 3798
- 3799
- 3800
- 3801
- 3802
- 3803
- 3804 function _safe_divide($x, $y)
- 3805 {
- 3806 if (MATH_BIGINTEGER_BASE === 26) {
- 3807 return (int) ($x / $y);
- 3808 }
- 3809
- 3810
- 3811 return ($x - ($x % $y)) / $y;
- 3812 }
- 3813 }